package leetcode_300;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class ContainsDuplicateII_219 {

	public static void main(String[] args) {
		ContainsDuplicateII_219 test=new ContainsDuplicateII_219();
		System.out.println(test.containsNearbyDuplicate(new int[] {1,2,3,1}, 3));

	}
	
	/**
	 * describe:类似哈希表 但是如果出现边界值 会出现非常大的情况
	 * 2018年6月15日 下午6:16:26
	 */
	public boolean containsNearbyDuplicate1(int[] nums, int k) {
        int max=Integer.MIN_VALUE;
        int min=Integer.MAX_VALUE;
        for(int i:nums) {
        	if(i>max)
        		max=i;
        	if(i<min)
        		min=i;
        }
        int []help=new int[max-min+1] ;//里面只保存最小出现的数的坐标;
        Arrays.fill(help, -1);
        for(int i=0;i<nums.length;++i) {
        	int location=nums[i]-min;
        	if(help[location]==-1) {
        		help[location]=i;
        	}
        	else {
        			if(i-help[location]<=k)
        				return true;
        			else
        				help[location]=i;
        	}
        }
        return false;
    }
	
	/**
	 * describe:用map AC 26%
	 * 2018年6月15日 下午6:23:30
	 */
	public boolean containsNearbyDuplicate(int[] nums, int k){
		if(nums.length<=1)
			return false;
		Map<Integer,Integer> map=new HashMap<Integer,Integer>();
		for(int i=0;i<nums.length;++i) {
			Integer may=map.get(nums[i]);
			if(may==null)
				map.put(nums[i], i);
			else {
				if(i-may<=k)
					return true;
				else
					map.put(nums[i], i);
			}
		}
		return false;
	}
	
	/**
	 * describe:用set AC 100% 每次进入值的时候 判断数量 如果数量多了 就删减
	 * 2018年6月15日 下午6:23:53
	 */
	public boolean containsNearbyDuplicate2(int[] nums, int k) {
        if (k > 3000) return false;
        if(nums.length < 2 || k < 1){
            return false;
        }
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < nums.length; i++){
            if(set.contains(nums[i]))
                return true;
            set.add(nums[i]);
            if(set.size() > k)
                set.remove(nums[i-k]);
        }
        return false;
    }

}
